#week3作业
from collections import defaultdict

#词典；每个词后方存储的是其词频，词频仅为示例，不会用到，也可自行修改
Dict = {"经常":0.1,
        "经":0.05,
        "有":0.1,
        "常":0.001,
        "有意见":0.1,
        "歧":0.001,
        "意见":0.2,
        "分歧":0.2,
        "见":0.05,
        "意":0.05,
        "见分歧":0.05,
        "分":0.1}

#待切分文本
sentence = "经常有意见分歧"

#实现全切分函数，输出根据字典能够切分出的所有的切分方式
def all_cut(sentence, Dict):
    res = defaultdict(list)
    for i in range(len(sentence)):
        if res.get(i) is None:
            res[i] = []
        s = sentence[:i+1] # 本轮要匹配的字符串
        vocabs = [ word for word in Dict.keys() if s.endswith(word)] # 本轮可以匹配的字符串
        for word in vocabs:
            length = len(word)
            if i-length >= 0:
                arr = res[i-length]
                for l in arr:
                    l1 = l.copy()
                    l1.append(word)
                    res[i].append(l1)
            else:
                res[i].append([word])
    return res[6]





if __name__=='__main__':
    print(all_cut(sentence, Dict))



#目标输出;顺序不重要
target = [
    ['经常', '有意见', '分歧'],
    ['经常', '有意见', '分', '歧'],
    ['经常', '有', '意见', '分歧'],
    ['经常', '有', '意见', '分', '歧'],
    ['经常', '有', '意', '见分歧'],
    ['经常', '有', '意', '见', '分歧'],
    ['经常', '有', '意', '见', '分', '歧'],
    ['经', '常', '有意见', '分歧'],
    ['经', '常', '有意见', '分', '歧'],
    ['经', '常', '有', '意见', '分歧'],
    ['经', '常', '有', '意见', '分', '歧'],
    ['经', '常', '有', '意', '见分歧'],
    ['经', '常', '有', '意', '见', '分歧'],
    ['经', '常', '有', '意', '见', '分', '歧']
]

